package lizhe;

import java.util.*;

/**
 * 两个数组的交集 II
 * <p>
 * 给你两个整数数组nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
 */
public class Intersect {

    public static int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        List<Integer> resultList = new ArrayList<>();

        int i1 = 0, i2 = 0, index = 0;
        do {
            if (nums1[i1] < nums2[i2]) {
                i1++;
            } else if (nums1[i1] > nums2[i2]) {
                i2++;
            } else {
                resultList.add(nums1[i1]);
                i1++;
                i2++;
            }
        } while (i1 < nums1.length && i2 < nums2.length);

        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }

        return result;
    }

    public static void main(String[] args) {
        intersect2(new int[]{1, 2, 2, 1}, new int[]{2, 2});
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        // 使用Map统计每个数组中元素的出现次数
        Map<Integer, Integer> counter1 = new HashMap<>();
        Map<Integer, Integer> counter2 = new HashMap<>();

        for (int num : nums1) {
            counter1.put(num, counter1.getOrDefault(num, 0) + 1);
        }

        for (int num : nums2) {
            counter2.put(num, counter2.getOrDefault(num, 0) + 1);
        }

        // 找到两个Map中共同的键，计算它们出现的最小次数
        List<Integer> resultList = new ArrayList<>();
        for (int key : counter1.keySet()) {
            if (counter2.containsKey(key)) {
                int minCount = Math.min(counter1.get(key), counter2.get(key));
                for (int i = 0; i < minCount; i++) {
                    resultList.add(key);
                }
            }
        }

        // 将List转换为数组
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }

        return result;
    }
}
